package class04;

/**
 * LeetCode 135. 分发糖果
 * 
 * 题目描述：
 * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
 * 你需要按照以下要求，给这些孩子分发糖果：
 * 1. 每个孩子至少分配到 1 个糖果。
 * 2. 相邻两个孩子评分更高的孩子会获得更多的糖果。
 * 
 * 示例：
 * 输入：ratings = [1,0,2]
 * 输出：5
 * 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
 * 
 * 输入：ratings = [1,2,2]
 * 输出：4
 * 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
 * 第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
 * 
 * 进阶问题：
 * 在基础问题上增加一个条件：
 * 3. 若相邻两个孩子评分一样，获得的糖果数可以不一样
 * 
 * 解题思路：
 * 1. 基础解法使用两次遍历：
 *    - 从左到右遍历，保证右边评分高的孩子比左边获得更多糖果
 *    - 从右到左遍历，保证左边评分高的孩子比右边获得更多糖果
 *    - 取两次遍历结果的最大值作为该孩子应得的糖果数
 * 
 * 2. 空间优化解法通过观察递减序列的规律，避免使用额外数组
 * 
 * 3. 进阶问题解法处理相等评分的情况，允许相同评分的孩子获得不同数量的糖果
 */
// 测试链接 : https://leetcode.com/problems/candy/
public class Code05_CandyProblem {

	// 这是原问题的优良解
	// 时间复杂度O(N)，额外空间复杂度O(N)
	// 使用两次遍历的方法：
	// 1. 从左到右遍历，保证右边评分更高的孩子比左边的孩子获得更多糖果
	// 2. 从右到左遍历，保证左边评分更高的孩子比右边的孩子获得更多糖果
	// 3. 取两次遍历结果的最大值作为每个孩子的糖果数
	public static int candy1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		// left数组记录从左到右遍历时每个孩子应得的糖果数（相对于左侧邻居）
		int[] left = new int[N];
		// 从左到右遍历，如果右侧孩子评分高于左侧，则其糖果数应该比左侧多1
		for (int i = 1; i < N; i++) {
			if (arr[i - 1] < arr[i]) {
				left[i] = left[i - 1] + 1;
			}
		}
		// right数组记录从右到左遍历时每个孩子应得的糖果数（相对于右侧邻居）
		int[] right = new int[N];
		// 从右到左遍历，如果左侧孩子评分高于右侧，则其糖果数应该比右侧多1
		for (int i = N - 2; i >= 0; i--) {
			if (arr[i] > arr[i + 1]) {
				right[i] = right[i + 1] + 1;
			}
		}
		int ans = 0;
		// 对于每个孩子，取左右两次遍历结果的最大值，确保同时满足左右邻居的约束
		for (int i = 0; i < N; i++) {
			ans += Math.max(left[i], right[i]);
		}
		// 每个孩子至少获得1颗糖果，而上面计算的是额外的糖果数，所以要加上N
		return ans + N;
	}

	// 这是原问题空间优化后的解
	// 时间复杂度O(N)，额外空间复杂度O(1)
	// 通过观察递减序列的规律，避免使用额外数组存储所有信息
	public static int candy2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// 找到从位置0开始的第一个非递增序列的结束位置
		int index = nextMinIndex2(arr, 0);
		// 计算第一个递减序列的糖果总数
		int res = rightCands(arr, 0, index++);
		// lbase表示左侧递增序列的基准值（最右端的糖果数）
		int lbase = 1;
		int next = 0;
		// rcands表示右侧递减序列的糖果总数
		int rcands = 0;
		// rbase表示右侧递减序列的基准值（最左端的糖果数）
		int rbase = 0;
		// 从index位置继续处理剩余元素
		while (index != arr.length) {
			// 如果当前孩子评分高于前一个孩子
			if (arr[index] > arr[index - 1]) {
				// 左侧基准值加1，并累加到总糖果数
				res += ++lbase;
				index++;
			// 如果当前孩子评分低于前一个孩子
			} else if (arr[index] < arr[index - 1]) {
				// 找到下一个非递减序列的结束位置
				next = nextMinIndex2(arr, index - 1);
				// 计算当前递减序列的糖果总数
				rcands = rightCands(arr, index - 1, next++);
				// 计算当前递减序列的基准值
				rbase = next - index + 1;
				// 根据左右基准值决定如何合并两个序列
				res += rcands + (rbase > lbase ? -lbase : -rbase);
				// 重置左侧基准值
				lbase = 1;
				// 移动索引到下一个处理位置
				index = next;
			// 如果当前孩子评分等于前一个孩子
			} else {
				// 给当前孩子分配1颗糖果
				res += 1;
				// 重置左侧基准值
				lbase = 1;
				index++;
			}
		}
		return res;
	}

	// 寻找从start开始向右的第一个非递减序列的结束位置
	public static int nextMinIndex2(int[] arr, int start) {
		for (int i = start; i != arr.length - 1; i++) {
			// 如果当前元素小于等于下一个元素，则找到了非递减的位置
			if (arr[i] <= arr[i + 1]) {
				return i;
			}
		}
		// 如果一直递减到末尾，则返回最后一个位置
		return arr.length - 1;
	}

	// 计算从left到right范围内的递减序列所需糖果总数
	// 假设最右边的孩子有1颗糖果，向左递增
	public static int rightCands(int[] arr, int left, int right) {
		int n = right - left + 1;
		// 等差数列求和公式：1+2+...+n = n*(n+1)/2
		return n + n * (n - 1) / 2;
	}

	// 这是进阶问题的最优解，不要提交这个
	// 时间复杂度O(N), 额外空间复杂度O(1)
	// 处理相等评分的情况，相同评分的孩子可以得到不同数量的糖果
	public static int candy3(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// 找到从位置0开始的第一个非严格递减序列的结束位置
		int index = nextMinIndex3(arr, 0);
		// 计算第一个递减序列的糖果总数和基准值
		int[] data = rightCandsAndBase(arr, 0, index++);
		int res = data[0];
		// lbase表示左侧递增序列的基准值（最右端的糖果数）
		int lbase = 1;
		// same表示连续相等评分的孩子数量
		int same = 1;
		int next = 0;
		// 循环处理剩余元素
		while (index != arr.length) {
			// 如果当前孩子评分高于前一个孩子
			if (arr[index] > arr[index - 1]) {
				// 左侧基准值加1，并累加到总糖果数
				res += ++lbase;
				// 重置相同评分计数
				same = 1;
				index++;
			// 如果当前孩子评分低于前一个孩子
			} else if (arr[index] < arr[index - 1]) {
				// 找到下一个非严格递减序列的结束位置
				next = nextMinIndex3(arr, index - 1);
				// 计算当前递减序列的糖果总数和基准值
				data = rightCandsAndBase(arr, index - 1, next++);
				// 根据左右基准值决定如何合并两个序列
				if (data[1] <= lbase) {
					res += data[0] - data[1];
				} else {
					res += -lbase * same + data[0] - data[1] + data[1] * same;
				}
				// 更新索引到下一个处理位置
				index = next;
				// 重置左侧基准值
				lbase = 1;
				// 重置相同评分计数
				same = 1;
			// 如果当前孩子评分等于前一个孩子
			} else {
				// 给当前孩子分配与左侧孩子相同的基准值
				res += lbase;
				// 增加相同评分计数
				same++;
				index++;
			}
		}
		return res;
	}

	// 寻找从start开始向右的第一个严格递减序列的结束位置
	public static int nextMinIndex3(int[] arr, int start) {
		for (int i = start; i != arr.length - 1; i++) {
			// 如果当前元素小于下一个元素，则找到了非递减的位置
			if (arr[i] < arr[i + 1]) {
				return i;
			}
		}
		// 如果一直非递增到末尾，则返回最后一个位置
		return arr.length - 1;
	}

	// 计算从left到right范围内的非严格递减序列所需糖果总数和基准值
	public static int[] rightCandsAndBase(int[] arr, int left, int right) {
		// base表示当前序列中最左侧孩子的糖果数（即基准值）
		int base = 1;
		// cands表示整个序列的糖果总数
		int cands = 1;
		// 从右到左计算每个孩子的糖果数
		for (int i = right - 1; i >= left; i--) {
			// 如果当前孩子评分等于右侧孩子评分
			if (arr[i] == arr[i + 1]) {
				// 当前孩子获得与右侧孩子相同的糖果数
				cands += base;
			// 如果当前孩子评分高于右侧孩子评分
			} else {
				// 当前孩子获得比右侧孩子多1颗糖果
				cands += ++base;
			}
		}
		// 返回糖果总数和基准值
		return new int[] { cands, base };
	}

	public static void main(String[] args) {
		int[] test1 = { 3, 0, 5, 5, 4, 4, 0 };
		System.out.println(candy2(test1));

		int[] test2 = { 3, 0, 5, 5, 4, 4, 0 };
		System.out.println(candy3(test2));
	}

}
